We present several algorithms for computing the visibility polygon of a simple polygon P of n vertices (out of which r are reflex) from a viewpoint inside P, when P resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in O (n (r) over bar) time, where (r) over bar denotes the number of reflex vertices of P that are part of the output. Whenever we are allowed to use O(s) variables, the running time decreases to O (nr/2(s) + n log(2) r) (or O (nr/2(s) + n log r) randomized expected time), where s is an element of O (log r). This is the first algorithm in which an exponential space-time trade-off for a geometric problem is obtained. (C) 2014 Elsevier B.V. All rights reserved.
展开▼
机译：当P驻留在只读存储器中且仅可使用很少的工作变量时，我们提出了几种算法，用于从P内的视点计算n个顶点的简单多边形P（其中r为反射）的可见性多边形。第一种算法使用恒定数量的变量，并以O为单位输出可见性多边形的顶点（n（r）跨栏），其中bar上的（r）表示作为输出一部分的P的反射顶点的数量。 。只要允许我们使用O（s）变量，运行时间就会减少到随机预期的O（nr / 2（s）+ n log（2）r）（或O（nr / 2（s）+ n log r））时间），其中s是O的元素（log r）。这是第一个获得几何问题的指数时空折衷的算法。 （C）2014 Elsevier B.V.保留所有权利。
展开▼
